\chapter{Experimenty}

V predchádzajúcej časti sme si navrhli a naimlementovali metódu ProSSiGen. Pre zhodnotenie chodu a presnosti metódy je proces testovania metódy nevyhnutný. V tejto kapitole si popíšeme metodiku testovania, z daných výsledkov určíme presnosť metódy, rozanalyzujeme výsledky a samotnú metódu, a riešenia pre zlepšenie.

\section{Metodika testovania}

Po návrhu a implementácii novej metódy typicky nasleduje krok determinácie úspešnosti danej metódy. Podstatou tohto kroku je automatizovaná klasifikácia proteínových štruktúr, ktorá sa následne skontroluje podľa manuálnej klasifikácie SCOP.

Na testovanie použijeme množiny dát, na ktorej sa testovala metóda Vorolign~\cite{birzele07}. Za účelom určenia presnosti tieto množiny ďalej využívali aj mnohé iné metódy.

Spomínané množiny proteínových štruktúr sú dané výťahom databázy ASTRAL-25 v1.65~\cite{chandonia04}, ktorá obsahuje 4357 štruktúr. Množina, ktorá obsahuje štruktúry, ktoré budeme klasifikovať predstavuje rozdiel SCOP databáz verzií v1.67 a v1.65 a je tvorená 979 štruktúrami. V našom kontexte ich budeme rozlišovať ako klasifikované a neklasifikované štruktúry. Pre dvojice klasifikovaná-neklasifikovaná štruktúra platí, že ich sekvencie sú si podobné na najviac 25\%.
 
Ďalej sa zameriame na vplyv genetického programovania pri porovnávaní konkrétnej dvojice štruktúr. Vyberieme si dvojicu štruktúr, na ktorej budeme sledovať vplyv zmeny jednotlivých parametrov pre algoritmy GP.

Testovanie prebiehalo na počítači s konfiguráciou 2xCPU Xeon X5660 2.8GHz, 24GB RAM, 500GB WD Velociraptor vo virtualizovanom OS Debian 6.0.6. Nakoľko sú testy časovo náročné, pre každú porovnávajúcu dvojicu štruktúr sme nastavili maximálny čas porovnávania 15 sekúnd a spustili sme niekoľko desiatok (60--80) inštancií programu, pričom každý využíval práve jedno vlákno procesora.

\section{Presnosť klasifikácie}

Testovanie našej metódy prebiehalo na približne polovici dostupných testovacích štruktúr. Už z týchto výsledkov môžeme dedukovať charakter metódy. Úspešnosť klasifikácie triedy sa pohybuje na úrovni približne 35\%, na úrovni rodu sú to 4\%, na úrovni nadrodiny, rodiny a celkovej zhody sú to len 2\%.

V tabuľke nižšie~\ref{table:main_results} môžeme vidieť percentuálne úspešnosti iných metód, ktorých dáta sme použili z prác od Hokszu a Galgonka~\cite{hoksza10b}~\cite{galgonek11}. Jedná sa o metódy SProt~\cite{galgonek11}, db-iTM~\cite{hoksza10b}, Vorometric-TM~\cite{sacan08}, Vorolign~\cite{birzele07} a BLAST~\cite{altschul97}.

Naša metóda teda veľmi zaostáva oproti napr. BLAST, čo je metóda využíva\hyp júca striktne sekvenčné podobnosti. Oproti sofistikovanejším metódam ako SProt, Vorolign~\footnote{Vorolign je metóda využívajúca dynamické programovanie na globálnej úrovni za použitia ohodnocovacích matíc a využívaním princípov Voronových diagramov.}, db-iTM a Vorometric-TM, naša metóda ešte viac zaostáva. Posledné dve vymenované metódy sú založené na tzv. TM-score~\cite{zhang04}, ktoré vo väčšine prípadov predstavuje relevantnejšie ohodnotenie ako napr. RMSD.

\begin{table}[h!]
\centering
\begin{tabular}{lcccc}
\firsthline
Metóda & Rodina & Nadrodina & Rod & Trieda \\
\hline
SProt & 90.7 & 96.9 & 98.6 & - \\
db-iTM 		& 86.6 & 95.8 & 98.2 & - \\
Vorometric-TM & 90.7 & 94.9 & 97.6 & -\\
Vorolign & 86.4 & 92.4 & 97.7 & - \\
BLAST 		& 48.9 & 52.5 & 52.8 & - \\
\lasthline
\end{tabular}
\caption{Úspešnosti klasifikácie metód na jednotlivých úrovniach}
\label{table:main_results}
\end{table}

\section{Analýza výsledkov}

Pripomeňme, že testovanie metódy prebiehalo len na určitej časti množiny neklasifikovaných štruktúr, takže odchýlka môže mať ešte určitú hodnotu. Ďalej uvážme všetky dvojice štruktúr, ktoré sa porovnávali a fakt, že priebeh evolučného procesu bol negatívne ovplyvnený troma hlavnými bodmi: 
\begin{itemize}
\item obmedzenou dobou chodu porovnávania jednej dvojice,
\item obmedzeným počtom generácií a
\item komplexnou implementáciou základných operácií GP.
\end{itemize}

Pre praktickosť testovania sa zvolila maximálna doba porovnávania jednej dvojice štruktúr (15 sekúnd). Je to kvôli tomu, že vývoj populácie, v ktorej sa nachádzajú jedinci s rozmanitou a zložitejšou štruktúrou, aplikácia kríženia a mutácie môže byť časovo náročnejšia. Inak by sme mohli predpokladať, že po dlhšej dobe a po mnohých vygenerovaných populáciách by sme získali veľmi dobré výsledky.

Typická situácia, ktorá nastáva v GP, je, že po určitej dobe algoritmus nie je schopný vyprodukovať \uv{lepších} jedincov, t.j. hodnota fitness konverguje. To normálne nastáva po určitom počte generácií. V teste sme použili hornú hranicu 2000 generácií. Tiež platí, že pre každú dvojicu táto hranica by mala byť odlišná (kvôli rozmanitosti štruktúr), no vopred túto hranicu pre každú dvojicu určiť nevieme.

Komplexnou implementáciou základných operácií GP rozumieme obšírne preskúmanie možností operácií GP, ktoré sú aspoň dostatočne implementované. Pri algoritmoch GP niekedy stačí doimplementovať práve jednu operáciu na to, aby sa výsledky evolúcie zlepšili rádovo o desiatky percent. Je teda isté, že spôsoby v~našej metóde nie sú dostatočné aj napriek tomu, že sme vo všeobecnosti pokryli nemalú časť možností.

Ako následok prvých dvoch vyššie spomínaných bodov je, že všetky generácie sa nemusia stihnúť vyvinúť. V našom testovaní je to až 85\% percent. To znamená, že algoritmy GP potrebujú viac času alebo ďalšie rozšírenia a implementáciu detailov.

\section{Vplyv parametrov genetického porovnania}

V testovaní sme používali nasledovné hodnoty dôležitých parametrov:\\
\textit{počet generácií: 2000},\\
\textit{pravdepodobnosť kríženia: 80\%},\\
\textit{pravdepodobnosť reprodukcie: 20\%} a\\
\textit{parameter Selective pressure: 1.8}.

Na grafe~\ref{fig:default_param} znázorňujúcom priebehy hodnoty \textit{fitness} vzhľadom na počet vygenerovaných populácií nám na danej dvojici poskytuje prehľad dôvodov, ktoré dokazujú, že zarovnanie proteínových štruktúr sa dokáže zlepšovať. 

\begin{figure}[h!]
	\centering
	\includegraphics[width=140mm]{../obr/graf_dvojic1.eps}
	\caption{Porovnanie priebehu RMSD v evolúci zarovnania dvojíc štruktúr 1OYIa a 1ADRa počas 100 000 generácií}
	\label{fig:default_param}
\end{figure}

Môžeme pozorovať, že po určitej generácii sa nám hodnota RMSD ustáluje a výrazne sa už nemení. Najväčší skok v hodnôt nastáva po 10000. generácii. Ďalej môžeme vidieť, že obmedzenie kríženia jedincov nám pomáha pri ohodnocovaní. Z toho môžeme vyvodiť, že kríženie v našich stromových štruktúrach niekedy zbytočne generuje nevhodné párovania.

Uvedomme si, že vykonané testy prebiehali len na najviac 2000 generáciách, čo nie je postačujúce. Avšak z časového hľadiska nie je veľmi prípustné, aby nová metóda potrebovala veľa času na kvalitné výsledky.

\begin{figure}[h!]
	\centering
	\includegraphics[width=140mm]{../obr/graf_dvojic2.eps}
	\caption{Porovnanie priebehu RMSD v evolúci zarovnania dvojíc štruktúr 1OYIa a 1ADRa počas 600 000 generácií}
	\label{fig:longer_param}
\end{figure}

Priebeh hodnoty RMSD na grafe~\ref{fig:longer_param} tiež značí, že rapídnejšia zmena v hodnote RMSD môže nastať aj po 100 000. generácii --- ako vidíme na modrej krivke. V takom prípade by algoritmy GP potrebovali ešte viac času na to, aby vyprodukovali adekvátne zarovnanie.

\section{Návrhy rozšírenia}

Prvý návrh rozšírenia by mohol predstavovať sofistikovanejšie ohodnocovanie stromovej štruktúry a celého jedinca. Predstavme si, že každá dvojica spárovaných a-sfér by mohla mať vo svojom spoločnom koreni hodnotu podobnosti. Spočítali by sme ju využívajúc ostatné rezíduá patriace do týchto a-sfér, ktoré sa nachádzajú na \textit{upstream} a \textit{downstream backbone}. Podobným štýlom by sme mohli ohodnocovať jednotlivé spárované dvojice SSE objektov a hodnotu uložiť do APSSE.

Ohodnocovanie jednotlivých uzlov by sa dalo následne využiť pri operácii náhodnej mutácie. Ak by ohodnotenie dvojice objektov bolo dobré, náhodná mutácia by mala menšiu šancu na uplatnenie. Naopak, horšie ohodnotenie dvojice objektov by ponúklo uplatnenie na náhodnú zmenu, resp. preusporiadanie.

Druhý návrh by spočíval v implementácii mutačných operácií, ktoré by preusporiadavali dvojice SSE objektov v rámci susedných APSSE objektov. Táto možnosť by mala rapídne zlepšiť evolučný priebeh.

Posledný návrh nesúci veľký význam a nové možnosti by bol pridanie ďalšej úrovne do stromovej štruktúry. Predstavme si aplikáciu mutačnej operácie, kedy dvojicu a-sfér odstránime z vektora AP a-sfér. Miesto zmazania by sme ich len skopírovali a pôvodné a-sféry by sme zmenili na zderivovaný objekt, ktorý by niesol informáciu, že dotyčné a-sféry sa ohodnocovaní jedinca nemajú brať do úvahy. Tieto a-sféry by sa v skutočnosti tvárili, akoby tam neboli. Na obrázku~\ref{fig:new_level} zderivované a-sféry a jej príslušný APSSE objekt majú vyfarbený uzol šedou farbou. Po tejto zmene by mohla nastať situácia, kedy by sme chceli do vektora napojiť susedné a-sféry. Miesto klasického napojenia do vektoru by sa však susedné a-sféry napojili priamo na derivované a-sféry a vytvorili by tak novú úroveň.

\begin{figure}
\centering
\begin{tikzpicture}[level distance=1.25cm,
  level 1/.style={sibling distance=1.5cm},
  level 2/.style={sibling distance=1.5cm},
  level 3/.style={sibling distance=1.25cm}]
    \tikzstyle{every node}=[draw]
    \node[right of=1st_tree,node distance=4cm] (2nd_tree) {\scriptsize{X|X}}
    	child { node[circle] {} 
        	child { node[circle] {$1^{A}_{X}$} }
        	child { node[circle] {$1^{B}_{X}$} }
        }
    ;
\end{tikzpicture}
$ $ \\
$ $ \\
\begin{tikzpicture}[level distance=1.25cm,
  level 1/.style={sibling distance=1.5cm},
  level 2/.style={sibling distance=1.5cm},
  level 3/.style={sibling distance=1.25cm}]
     \tikzstyle{every node}=[draw]
    \node[fill=black!5] (1st_tree) {\scriptsize{X|X}}
    	child { node[circle,fill=black!5] {} 
        	child { node[circle,fill=black!5] {$1^{A}_{X}$} }
        	child { node[circle,fill=black!5] {$1^{B}_{X}$} }
        }
    ;
    \node[right of=1st_tree,node distance=4cm] (2nd_tree) {\scriptsize{X|NIL}}
    	child { node[circle] {} 
        	child { node[circle] {$1^{A}_{X}$} }
        	child { node[circle] {null} }
        }
    ;
    \node[right of=2nd_tree,node distance=3cm] (3rd_tree) {\scriptsize{NIL|X}}
    	child { node[circle] {} 
        	child { node[circle] {null} }
        	child { node[circle] {$1^{B}_{X}$} }
        }
    ;
\end{tikzpicture}
$ $ \\
$ $ \\
\begin{tikzpicture}[level distance=1.25cm,
  level 1/.style={sibling distance=1.5cm},
  level 2/.style={sibling distance=1.5cm},
  level 3/.style={sibling distance=1.25cm}]
     \tikzstyle{every node}=[draw]
    \node[] (1st_tree) {\scriptsize{X|NIL}}
    child { node[circle] {}
        child { node[circle,fill=black!5] {$1^{A}_{X}$} 
			child { node[circle] {$1^{A}_{X}$} }	        
        }
        child { node[circle,fill=black!5] {$1^{B}_{X}$} 
        	child { node[circle] {null} }
        }
      }
    ;
    \node[draw=none,right of=1st_tree,node distance=4cm] (2nd_tree) {}
    ;
    \node[right of=2nd_tree,node distance=3cm] (3rd_tree) {\scriptsize{NIL|X}}
    	child { node[circle] {} 
        	child { node[circle] {null} }
        	child { node[circle] {$1^{B}_{X}$} }
        }
    ;
\end{tikzpicture}
\caption{Vznik novej úrovne v stromovej reprezentácii}
\label{fig:new_level}
\end{figure}

Nová úroveň stromu by takto niesla informáciu, ako stromová štruktúra vyzerala v minulosti. Na základe tohto poznatku by sa dali vyvodzovať ďalšie závery a napr. aj sofistikovanejšie ohodnotenia celého jedinca. Vytvorením novej úrovne sa začíname približovať k lamarkizmu. Tento smer môže priniesť ďalšie zlepšenia v evolučnom procese.

Zo spomenutých navrhnutých riešení by implementácia pridanej úrovne bola možno príliš zložitá, resp. réžia zostavovania stromovej štruktúry by bola náročná a preto je otázne, či by toto rozšírenie bolo vhodné. Navyše sme boli limitovaní výpočtovými zdrojmi, čo by nám ešte viac sťažovalo priebeh testovania. Celému riešeniu by najviac pomohla implementácia mutačných operátorov, ktoré by pracovali na úrovni SSE.